package com.atwulidun.dynamicprogramming03.knapsackproblem.spacialrefined;

import java.util.Arrays;
// 对于0-1背包(进行了空间优化)：
// 一、问题描述：
// 一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
// 二、问题分析：
// 状态转移方程：dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i])
// 由上述状态转移方程可知，dp[i][j]的值只与dp[i-1][0,...,j-1]有关，所以我们可以采用动态规划常用的方法（滚动数组）对空间进行优化（即去掉dp的第一维）。
// 需要注意的是，为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向枚举（空间优化前没有这个限制），伪代码为：
// 01背包问题伪代码(空间优化版)
// dp[0,...,W] = 0
// for i = 1,...,N
//     for j = W,...,w[i] // 必须逆向枚举!!!
//         dp[j] = max(dp[j], dp[j−w[i]]+v[i])
// 三、对于逆向枚举的理解：
// 空间优化前：dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i])
// 空间优化后：dp[j] = max(dp[j], dp[j−w[i]]+v[i])
// 注意空间优化后的状态转移方程两边的是2个状态(左边的是当前状态，右边的是上一状态（二维的通过i可以看出来）)
// dp[i][j]是由dp[i-1][j-w[i]]推出来的,现在要把二维的改成一维的,即要推dp[j],要保证dp[j]由dp[j-w[i]]推出来，
// 如果v是顺序递增的,则相当于dp[i][j]变得是由dp[i][j-w[i]]推出来的,而不是由原来的dp[i-1][j-w[i]]推的
// 四、空间优化后必须要逆向具体例子：
// 设有3件物品 ,背包能容纳的总重量为10
//i=1,2,3
//
//物品号         重量(w)          价值(v)
//i=1             4                 5
//
//i=2             7                 9
//
//i=3             5                 6
//
//dp[j] = max(dp[j], dp[j−w[i]]+v[i])
//
//如果j是顺序递增 i=1时，j=4~10 （因为j要至少大于等于w[i]嘛 不然减出个负数没意义）
//
//-------------------  i=1  ---------------
//j=4:
//dp[4]=max{dp[4],dp[0]+5}    max{0,5}=5   dp[4]=5
//
//j=5:
//dp[5]=max{dp[5],dp[1]+5}    max{0,5}=5   dp[5]=5
//
//j=6:
//dp[6]=max{dp[6],dp[2]+5}    max{0,5}=5   dp[6]=5
//
//j=7:
//dp[7]=max{dp[7],dp[3]+5}    max{0,5}=5   dp[7]=5
//
//j=8:
//dp[8]=max{dp[8],dp[4]+5}    max{0,10}=10  dp[8]=10  (这里显然不对,这时i=1，只能放一件物品,然而没有一个物品的价值为10的 )
//（也就是说这里的dp[4]用的是本次计算出来的dp[4]，而不是上一次的dp[4]）
//j=9:
//dp[9]=max{dp[9],dp[5]+5}    max(0,10}=10  dp[9]=10
//
//j=10:
//dp[10]=max{dp[10],dp[6]+5}  max{0,10}=10  dp[10]=10

public class ZeroOneKnapsackProblem {
    // 物体的重量
    private static int[] w = {1, 4, 3};
    // 物体的价值
    private static int[] v = {1500, 3000, 2000};
    // 背包的最大容量
    private static int maxWeight = 7;
    // 前i个物体能装入背包容量为j时的最大价值
    // 进行空间优化后dp由原来的二维数组变为一维数组
//    private static int[][] dp = new int[w.length + 1][maxWeight + 1];
    private static int[] dp = new int[maxWeight + 1];
    // 记录背包装入的物体，需要为二维数组，因为要把第几个物体给区分开来
    private static int[][] path = new int[w.length + 1][maxWeight + 1];


    public static void main(String[] args) {
        // 对dp进行初始化，全部设置全为0
        Arrays.fill(dp,0);

        // 动态地将物品装入背包
        // 外层循环控制物体
        // 注意：这里是i<= w.length
        for (int i = 1; i <= w.length; i++) {
            // 内层循环控制背包容量，这里必须用逆向枚举
            for (int j = dp.length - 1; j > 0  ; j--) {
                // 如果当前物品的重量大于当前背包最大的容量
                // 注意：w的下标是从0开始，这里要减个1
                if (w[i - 1] > j) {
                    // 使用前i-1个物品的装入策略
                    dp[j] = dp[j];
                } else {
                    // 如果当前物品的重量小于等于当前背包的最大容量，这时要比较：
                    // 前i-1个物品的装入策略；装入当前物品，同时剩余空间再装前i-1个物品
                    // 注意：v的下标也是从0开始，故这里也要-1
                    if (dp[j] < v[i - 1] + dp[j - w[i - 1]]) {
                        dp[j] = v[i - 1] + dp[j - w[i - 1]];
                        // 特别注意：这里的path相当于一维数组充当二维数组的作用，要把是第几个物体记录下来
                        // 如果不为0，那么就不是使用前i-1个物品的装入策略
                        path[i][j] = 1;
                    } else {
                        dp[j] = dp[j];
                    }
                }
            }
        }

        // 对dp进行逆向遍历
        int i = path.length - 1;// 表示最后一件物体
        int j = path[0].length - 1;// 表示背包的最大容量
        while (i > 0 && j > 0) {
            // 如果背包的最大容量装入的是最后一件物体
            if (path[i][j] == 1) {
                System.out.println("第" + i + "件物品装入背包");
                j -= w[i - 1];// 求出剩余的空间
            }
            // 这里分两种情况：
            // 1.如果上面的if成立，那么i--是看剩余的空间是否装入了前一件物品
            // 2.如果上面的if不成立，那么i--是看当前空间是否装入了前一件物品
            i--;
        }
        for (int ints : dp) {
                System.out.print(ints + " ");
        }
        System.out.println();
        for (int[] ints : path) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}
